#include <stdio.h>
#include <string.h>
#include <stdlib.h>


// int fib(int n)
// {
// 	int *f,i,ret;
//     if(n < 2) return n;
//     else {
//         f = malloc((n+1)*sizeof(int));
//         f[0] = 0; f[1] = 1;
//         for(i=2; i<=n; i++)
//             f[i] = (f[i-1] + f[i-2])  % 1000000007;
//         ret = f[n];
//         free(f);
//         return ret;
//     }  
// }

int MOD = 1e9 + 7;
int memo[100] = {0,1,0};
int fib(int n) {
	if(n < 2 || memo[n]) return memo[n];
	memo[n] = (fib(n-1) + fib(n-2)) % MOD;
	return memo[n];
}


// 青蛙跳台阶问题
// 此类求 多少种可能性 的题目一般都有 递推性质 ，即 f(n)f(n)f(n) 和 f(n−1)f(n-1)f(n−1)…f(1)f(1)f(1) 之间是有联系的。
// int jumpFloor(int number ) {
//     if (number < 3) return number;
//     int i, f[number+1];	//注意是长度
//     f[0] = 0; f[1] = 1; f[2] = 2;
//     for (i = 3; i <= number; i++) { //注意推导起点
//         f[i] = f[i-1] + f[i-2];
//     }
//     return f[number];
// }


// 变种问题：变态跳台阶，每次跳的阶数不定
// 推导：
// f(n) = f(n-1) + f(n-2) + …… + f(1)
// f(n-1) =  f(n-2) + …… + f(1)
// 所以f(n) = 2*f(n-1)，初始f(1) = 1
int jumpFloorII(int number) {
	int f = 1, fn = 1;
	for (int i = 2; i <= number; i++) {
		fn = 2*f;
		f = fn;
	}
	return fn;
} 